/*
 * ApproxCliqueLifter.cpp
 *
 *  Created on: Jan 24, 2014
 *      Author: ik
 */

#include <ApproxCliqueLifter.h>

ApproxCliqueLifter::ApproxCliqueLifter(Grafo &grafo, Cliquer &cliquer, const SeparatorParameters& par) : CliqueLifter(grafo, cliquer),
		_parametros(par), _alpha(1), _vertices(*(new VertexSet(_grafo.getN()))), _enumerables(*(new Lista(_grafo.getN()))),
		_RR(*(new ProjectableCliqueSet(_grafo.getN()))), _R(*(new VertexSet(_grafo.getN()))),
		_pesosPD(*(new IntValueArray(_grafo.getN()))), _verticesPD(*(new VertexSet(_grafo.getN())))
{
}

ApproxCliqueLifter::~ApproxCliqueLifter()
{
	delete &_enumerables;
	delete &_RR;
	delete &_R;
	delete &_vertices;
	delete &_pesosPD;
	delete &_verticesPD;
}

int ApproxCliqueLifter::greedyCovering(VertexSet& R, const IntValueArray& pesos, int lim) {
	int size = 0;
	int weight = 0, cw;
	bool nemptcol = true;

	_R.copyAll(R);

	_enumerables.clear();
	_R.lista(_enumerables);
	_enumerables.decrecientePesos(pesos);

	while (size < lim && nemptcol) {
		_RR.copyAll(_R);
		nemptcol = false;
		cw = 0;

		for (int i = 0; i < _enumerables.cantidad(); i++) {
			int v = _enumerables[i];
			if (_RR.contains(v))
			{
				if (!nemptcol) {
					cw = pesos[v];
					nemptcol = true;
				}
				// note that vidx is removed from _RR only if clqOrStab=false
				_RR.retainAll(_grafo.vecinos(v));
				_RR.remove(v);
				_R.remove(v);
			}
		}

		if (nemptcol) {
			weight+=cw;
			size++;
		}
	}

	return weight;
}

int ApproxCliqueLifter::greedyPrimalDual(const VertexSet& R, const IntValueArray& pesos, int alpha, int lim) {
	_pesosPD.copy(pesos);
	_verticesPD.copyAll(R);

	int npd;
	int k = 0;
	do {
		_enumerables.clear();
		_verticesPD.lista(_enumerables);

		int menorp = _pesosPD[_enumerables[0]];
		int t;
		for (t = 1; t < _enumerables.cantidad(); t++)
			if (_pesosPD[_enumerables[t]] < menorp)
				menorp = _pesosPD[_enumerables[t]];
		npd = 0;
		for (t = 0; t < _enumerables.cantidad(); t++) {
			_pesosPD.setValue(_enumerables[t], _pesosPD[_enumerables[t]]-menorp);
			if (_pesosPD[_enumerables[t]] == 0)
				_verticesPD.remove(_enumerables[t]);
			else
				npd++;
		}
		k+=alpha*menorp;
	} while (npd > _parametros.SMALLGRAPH);

//	cout << "menorp: " << k << " sizevert: " << _vertices.size() << " sizevv: " << npd << endl;
	_RR.removeAll();
	return k + _cliquer.optimize(_pesosPD, _verticesPD, _RR, lim-k < 0 ? 0 : lim-k);
}

int ApproxCliqueLifter::calculaLambda(const VertexSet& soporte, const IntValueArray& coeficientes, VertexSet& proyectada, int pi)
{
	_vertices.copyAll(soporte);
	_vertices.removeAll(proyectada);

//	cout << "=======================================Desigualdad: ";
//	dv->print();
//	cout << "Clique: ";
//	W->print();
//	if (!_grafo.isClique(*W))
//		cout << "No es clique!!!!!!!!!!!!!!!" << endl;

	int valor;
	int newalpha;
	int nvert = _vertices.size();
	if (nvert <= _parametros.SMALLGRAPH) {
		_RR.removeAll();
		valor = _cliquer.optimize(coeficientes, _vertices, _RR, 0);
		newalpha = _RR.size();
		if (_alpha > newalpha)
			newalpha = _alpha;
//		cout << "  alpha: " << _alpha << "  new alpha: " << newalpha << " Lambda: " << lambda;
//		cout << endl;
//		cout << "exact weighted alpha: " << valor << " Lambda: " << lambda << " rhs: " << dv->getRHS() << endl;
//		cout << "Max weighted stable set of {soporte-clique}: ";
//		_RR.print();
	}
	else {
//		cout << "alpha before: " << _alpha;
		if (nvert <= (_parametros.SMALLGRAPH << 1)) {
			_RR.removeAll();
			newalpha = _cliquer.optimize(_vertices, _RR, _alpha, _alpha+1, 0);
		}
		else
			newalpha = _alpha+1;

		valor = greedyPrimalDual(_vertices, coeficientes, newalpha, 0);
//		cout << "  alpha: " << _alpha << "  new alpha: " << newalpha << " Lambda: " << lambda;
//		cout << endl;
//		cout << "casi exact weighted alpha: " << valor << " newalpha: " << newalpha << " Lambda: " << lambda << " rhs: " << dv->getRHS() << endl;
	}

	if (newalpha == _alpha) {
		_vertices.addAll(proyectada);
		if (nvert <= (_parametros.SMALLGRAPH << 1)) {
			_RR.removeAll();
			_alpha = _cliquer.optimize(_vertices, _RR, _alpha, _alpha+1, 0);
		}
		else
			_alpha++;
		_vertices.removeAll(proyectada);
//			cout << "  alpha after: " << _alpha;
	}
	else
		_alpha = newalpha;
//	cout << endl;

	return valor - pi;
}
